The invention pertains to digital data processing and, more particularly, to apparatus, systems and methods for data storage and retrieval. The invention has application, by way of non-limiting example, in the creation, updating and access of operational and analytic databases.
Databases store data within a framework known as a data model. Current data models include the network model, hierarchical model, object model, key-value model, graph model, document model and the relational model amongst others. The relational model is by far the most popular and ubiquitous in its use.
The relational model views data as relations or tables containing multiple rows and columns. Each relation stores information about a particular type of entity, such as employees and departments, with each row in a table storing information about one instance of the entity to which the table relates. Each column in the table is an attribute for the entity and contains a value in each row that corresponds to an entity instance. The set of table and column definitions is known as the database schema.
The following are example tables for Employees, Departments and Regions.
TABLE 1Employees TableCommissionDepartmentNameEmployee NumberSalaryRateNumberSimon Smith 1010000100John Jones202000010.00%200Bob Brown303000015.00%200
TABLE 2Departments TableNameDepartment NumberRegion NumberAdministration1002000Sales2001000Support3003000
TABLE 3Regions TableNameRegion NumberNorth1000East2000South3000West4000
SQL is a language used with relational databases to both define database schemas and to manipulate data stored within those schemas. The SQL statements to define the example tables above might be as follows:
 create table Employees (Name varchar(64) not null,  EmployeeNumber number primary key,  Salary number(8,2) not null,  CommissionRate number(4,2),  DepartmentNumber number references  Departments(Department Number));create table Departments (Name varchar(64) not null,  DepartmentNumber number primary key,  RegionNumber number references Regions(RegionNumber)); create table Regions (Name varchar(64) not null,  RegionNumber number primary key);
Each employee has a name and a unique employee number that are used to identify them; each employee has a salary and a commission plan and is employed by a single department. Each of these attributes for an employee are stored in a separate column in the table.
Similarly, each department has a name and number and is located in one region; each region has a name and number that identifies it.
Thus the “Smith” employee belongs to the “Administration” department which is in the “East” region. This is discerned from the department and region numbers that are common across the tables. These relationships are indicated by ‘primary key’ and ‘foreign key’ constraints in the above SQL statements,
Relational tables are typically normalized to remove any duplication of data contained within them. In the above example, it would be possible to rearrange the data into a single table such that a department's information is duplicated against every employee that belongs to that department. Such duplication is sub-optimal from both a storage size and update overhead perspective because every item of department data has to be stored and updated in multiple locations. The process of normalization moves groups of columns with duplicate data into a single row into a separate table.
Relational databases support the concept of a table join whereby rows from separate tables are joined together by a common column value such that all rows with a corresponding join column are correlated together. In the example above, the employee table may be joined to the department table by the department number column in both tables. Normalized data requires a join at query time to reproduce de-normalized data.
Relational databases are often used in two distinct ways—as an operational or analytical database. An operational (OLTP) database records and manages business process transactions. It provides a detailed and reliable reference for business procedures. Each transaction in an operational system is only likely to be interested in a handful of entity instances at any given time. In contrast, an analytical (OLAP) database provides a broad analysis across a large body of data. Conventionally, the data retained by an analytical system is less detailed than the operational system to assist with the performance of analytical queries.
When considered in a relational database context, an operational transaction or query is likely to touch a large proportion of columns across a very small proportion of rows; conversely, an analytical query is likely to touch a small proportion of columns in a very large proportion of rows. This has led to a trend in relational databases to organize operational databases in row orientation (complete rows stored together) and to organize analytical databases in column orientation (complete columns stored together). These approaches attempt to co-locate data in storage according to anticipated access patterns so that retrieval requests from storage are kept to a minimum.
Conventional operational and analytical databases are typically highly normalized and highly de-normalized respectively. Operational databases are highly normalized to avoid the overheads associated with the update of duplicated data; whereas analytical database are often de-normalized to avoid the overhead of joins at query time. This difference in approach to normalization creates a difference in the database schemas because different table definitions are required.
Therefore conventional relational databases are organized differently depending on whether an operational or analytical workload is anticipated. A highly normalized schema stored in row orientation is considered sub-optimal for analytical queries because the analytical queries are forced to process entire rows and perform extensive join processing; while a highly de-normalized schema in column orientation is considered sub-optimal for operational systems because of the spread of individual rows across multiple storage areas and the overhead of updating duplicated data.
With the flat table structure (row and column) so far described, is only possible to find a row that contains a specific column by scanning a whole table in a row store, or a whole column in column store. With very large sets this becomes a resource and time consuming process. To assist with this process, indexes are layered on top of the flat table structure to enable fast navigation to specific rows by column value. Indexes can take many forms and include mechanisms such as B-Trees, hashing, bit maps and partitioning amongst others. However, regardless of the form of indexing used, it is effectively performing part of the query processing work ahead of query time. In effect, indexing moves the overhead of query processing to data update time. This may be reasonable if the volume of query activity is much greater that update activity such as an analytical system—but this is not the case in operational systems or even in analytical systems that require constant updates.
Hence conventional operational and analytical databases are designed differently and while a single relational database can support operational or analytical workloads efficiently it typically cannot support both workloads at the same time within the same database instance. This often leads to the use of multiple database instances to support common data sets with each database designed differently to support different workloads. This creates complexity involving integration and data transformation activities, latency in data availability and additional capital and operational expenditure.
When considering the performance of a database architecture it is important to understand the hardware context in which it operates.
Current computer architectures consist of CPU, memory and storage components which operate at vastly different speeds. A contemporary CPU contains one or more CPU caches that have a limited size but operate at near CPU clock speed; main memory is typically much larger but operates at lower speeds because of the cost of fabrication of fast memory. Storage will typically operate at several orders of magnitude slower speed because of the different technologies used. Even flash storage typically operates at two orders of magnitude slower than main memory. The speed of these components can be expressed in fetch frequencies which measure the rate at which data fetch operations can be requested and fulfilled. The fetch frequency of a component is an inverse measure of its access latency.
As shown in FIG. 1, data is fetched from storage into memory, then fetched from memory into CPU cache. Data also moves in the opposite direction between these components, as illustrated.
If the CPU requires data that is not currently available in the CPU cache, it must make a request to fetch it from memory and/or storage. The CPU must then wait for the slower components to service the request and this is commonly known as a CPU stall. During a CPU stall, the CPU is unable to perform any useful work and this has an adverse effect on processor throughput and overall performance.
While fetch frequencies are radically different across computer components, the rate at which data can be transferred in bulk between components is much more similar. Therefore, to minimize the number and the affect of CPU stalls, computer components will bulk fetch data that is near the explicitly requested data address in the hope that the unsolicited data is relevant to the following CPU operations and avoid immediately subsequent fetch requests.
The bulk fetch strategy will only amortize a CPU stall if the unsolicited data is indeed relevant and useful to subsequent CPU operations; if not, the CPU will be forced into another stall until useful data is explicitly fetched to replace the unsolicited data. Bulk fetched data that is not useful can be viewed as cache pollution and degrades performance by engendering CPU stalls. Cache pollution occurs both in the CPU cache and within main memory when irrelevant data is fetched from storage.
To avoid cache pollution, it is necessary to align storage structures with the storage address dimension so that each bulk fetch pulls in information relevant to the current access path. This is known as good spatial locality.
Row oriented relational databases are designed to reduce cache pollution in operational workloads where whole rows are being queried by ensuring the rows are aligned with the address dimension. However, with analytical workloads where only specific columns are required, this storage orientation causes cache pollution because irrelevant columns are also fetched into cache.
Conversely, column oriented relational databases are designed to reduce cache pollution in analytical workloads where specific columns are being queried by ensuring the columns are aligned with the address dimension. However, with operational workloads where only specific rows are required, this orientation causes cache pollution because irrelevant rows are also fetched into cache.
For both row and column orientated storage, cache will always be polluted by irrelevant rows where non-consecutive rows are required by a query.
Moreover, the use of hierarchical block structures, such as a B-Tree index, to navigate to rows also pollutes cache. Typically, only a part of each block fetched from the higher levels of a hierarchy will be relevant to a query, while the remainder of the block pollutes the cache. This is exacerbated by navigating down such hierarchies causing cache pollution at each step.
These hierarchical structures are routinely used in databases of both storage orientations.
An object of the invention is to provide improved apparatus, systems and methods for digital data processing.
A further object of the invention is to provide such apparatus, systems and methods as can be used for data storage and retrieval.
Yet a still further object of the invention is to provide such apparatus, systems and methods as can be utilized in support of legacy and new database models, schemas and workloads.
Yet a still further object of the invention is to provide such apparatus, systems and methods as support OLTP and OLAP activity independently of the data model, schema and/or workload.
Yet a still further object of the invention is to provide such apparatus, systems and methods as support such activity with improved efficiency and speed.